package leetcode.editor.cn;

//给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。 
//
// 进阶：
//
// 你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

// 示例 1：
//输入：nums = [3,0,1]
//输出：2
//解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。 
//
// 示例 2： 
//
//输入：nums = [0,1]
//输出：2
//解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。 
//
// 示例 3： 
//
//输入：nums = [9,6,4,2,3,5,7,0,1]
//输出：8
//解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。 
//
// 示例 4： 
//
//输入：nums = [0]
//输出：1
//解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。 
//
// 提示： 
// n == nums.length
// 1 <= n <= 104 
// 0 <= nums[i] <= n 
// nums 中的所有数字都 独一无二 
// 
// Related Topics 位运算 数组 哈希表 数学 排序 
// 👍 421 👎 0


import java.util.Arrays;

public class T268MissingNumber {
    public static void main(String[] args) {
        Solution solution = new T268MissingNumber().new Solution();
        int[] nums = {0,1,2,3,4,5,6,7,9};
        solution.missingNumber(nums);


    }

    class Solution {
        public int missingNumber(int[] nums) {
            //先排序
            Arrays.sort(nums);
            //首先判断排序后最后一个数是否等于数组长度，如果不相等，则说明丢失的数字就是最后一个数+1
            if (nums.length != nums[nums.length - 1]) {
                return nums[nums.length - 1] + 1;
            }
            //遍历找到相邻两个数之差不等于1的位置，丢失的数就是前一个数+1
            for (int i = 0; i < nums.length-1; i++) {
                if (nums[i + 1] - nums[i] != 1) {
                    return nums[i] + 1;
                }
            }
            return 0;
        }

        public int missingNumber1(int[] nums) {
            //直接用数学的方法发现，我们令一个数 a 等于 从1加到 nums.length；令数 b 等于nums中所有元素之和。
            //丢失的数字就等于 a-b；
            //有数据溢出的风险，可以边加边减
            int a = nums.length * (nums.length + 1) / 2, b = 0;
            for (int i = 0; i < nums.length; i++) {
                b= b+nums[i];
            }
            return a - b;
        }


        public int missingNumber2(int[] nums) {
            int a = nums.length * (nums.length + 1) / 2;
            for (int i = 0; i < nums.length; i++) {
                a = a - nums[i];
            }
            return a;
        }


        public int missingNumber3(int[] nums) {
            int a = 0;
            for (int i = 1; i <= nums.length; i++) {
                a = a + i;
                a = a - nums[i - 1];
            }
            return a;
        }

    }

}